package com.leetcode.partition1;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/9/22 9:05
 */
public class LC42接雨水 {

    public static int trap(int[] height) {
        return monotonicStack(height);
    }

    private static int monotonicStack(int[] height) {
        Stack<Integer> s = new Stack<>();           //存储下标
        int i = 0, answer = 0;
        while (i < height.length) {
            while (!s.isEmpty() && height[i] > height[s.peek()]) {          //栈顶元素不为空且当前柱子的高度大于栈顶柱子的高度，说明可以形成低洼
                int top = s.pop();
                if (s.isEmpty()) break;         //前面没有柱子或者没有更高的柱子
                int distance = i - s.peek() - 1;
                int boundedHeight = Math.min(height[i], height[s.peek()]) - height[top];
                answer += distance * boundedHeight;
            }
            s.push(i++);
        }
        return answer;
    }

    private static int dynamicProgramming(int[] height) {
        int[] leftMaxHeight = new int[height.length];           //leftMaxHeight[i]，截止当前左边的最大高度
        int[] rightMaxHeight = new int[height.length];          //rightMaxHeight[i]，截止当前右边的最大高度
        int answer = 0;
        leftMaxHeight[0] = height[0];
        rightMaxHeight[rightMaxHeight.length - 1] = height[height.length - 1];
        for (int i = 1; i < height.length; i++) leftMaxHeight[i] = Math.max(leftMaxHeight[i - 1], height[i]);
        for (int j = height.length - 2; j >= 0; j--) rightMaxHeight[j] = Math.max(rightMaxHeight[j + 1], height[j]);
        System.out.println(Arrays.toString(leftMaxHeight));
        System.out.println(Arrays.toString(rightMaxHeight));
        for (int i = 0; i < height.length; i++) {
            answer += Math.min(leftMaxHeight[i], rightMaxHeight[i]) - height[i];
        }
        return answer;
    }

    private static int doubleIndex(int[] height) {
        int answer = 0;
        for (int i = 0; i < height.length; i++) {
            if (i == 0 || i == height.length - 1) continue;     //第一个和最后一个不接雨水
            int leftMax = 0, rightMax = 0;
            for (int j = 0; j < i; j++) leftMax = Math.max(leftMax, height[j]);
            for (int j = i + 1; j < height.length; j++) rightMax = Math.max(rightMax, height[j]);
            int cur = Math.min(leftMax, rightMax) - height[i];
            if (cur > 0) answer += cur;
        }
        return answer;
    }

    public static void main(String[] args) {
        int[] height = {4, 2, 0, 3, 2, 5};
//        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap(height));
    }
}
